# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2019-03-22 11:24:21
# @LastEditTime: 2020-03-30 13:18:31
# @LastEditors: shj
# @Description: 堆排序
# @FilePath: /python3/algorithms/Heapsort.py
#
"""
堆排序
最坏时间复杂度	O(n log n)
最优时间复杂度	O(n log n)
平均时间复杂度	O(n log n)
最坏空间复杂度	O(1)

概述:
若以升序排序说明，把数组转换成最大堆积(Max-Heap Heap)，这是
一种满足最大堆积性质(Max-Heap Property)的二叉树：对于除了根
之外的每个节点i，有：A[parent(i)] ≥ A[i]。
重复从最大堆积取出数值最大的结点(把根结点和最后一个结点交换，
把交换后的最后一个结点移出堆)，并让残余的堆积维持最大堆积性质。

堆节点的访问:
父节点i的左子节点在位置 (2i+1);
父节点i的右子节点在位置 (2i+2);
子节点i的父节点在位置 floor((i-1)/2);

堆的操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节
点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位于第一个数据的根节点，并做最大堆
调整的递归运算
"""


def heap_sort(sort_list):
    """堆排序函数"""
    def max_heap(start, end):
        """大根堆调整"""
        # 初始化根节点索引
        root = start
        # 对构成的二叉树进行循环调整
        while True:
            # 子节点索引
            child = 2 * root + 1
            # 当对所有节点调整完后，跳出循环
            if child > end:
                break
            # 右子节点索引存在（未过界），且值大于左子节点，用右子节点进行判断
            if child + 1 <= end and sort_list[child] < sort_list[child + 1]:
                child += 1
            # 根节点的值小于子节点的值，调整根节点值（互换值），并更新根节点索引
            if sort_list[root] < sort_list[child]:
                sort_list[root], sort_list[child] = sort_list[
                    child], sort_list[root]
                root = child
            else:
                break

    # 创建大根堆
    # 从第一个非叶节点开始构建
    for start in range(len(sort_list) // 2 - 1, -1, -1):
        max_heap(start, len(sort_list) - 1)

    # 堆排序
    for end in range(len(sort_list) - 1, 0, -1):
        # 将最大值填入列表末尾，对剩下的节点进行根排序
        sort_list[0], sort_list[end] = sort_list[end], sort_list[0]
        max_heap(0, end - 1)
    return sort_list


def main():
    nosort_list = [12, 3, 34, 56, 21, 55, 4, 7, 51]
    print('no_sort_list: {}\nlength={}'.format(nosort_list, len(nosort_list)))
    sorted_list = heap_sort(nosort_list)
    print('sorted_list: {}'.format(sorted_list))


if __name__ == '__main__':
    main()
